Search results for "Bin packing problem"

New upper bounds for some instances from benchmark for vector packing problem

2021

This dataset is a result of the research: Đorđe Stakić, Miodrag Živković, Ana Anokić, "A Reduced Variable Neighborhood Search Approach to the Heterogeneous Vector Bin Packing Problem", Information Technology and Control, 2021, 50(4), 808-826, https://doi.org/10.5755/j01.itc.50.4.29009 Files are given by algorithm described in it. This dataset consists of 14 solutions with better bounds for instances described in paper: Heßler, K., Gschwind, T., Irnich, S. Stabilized branch-and-price algorithms for vector packing problems. European Journal of Operational Research, 2018, 271(2), 401-419. https://doi.org/10.1016/j.ejor.2018.04.047 File structure: Instance name: UB: solut…

Ensemble Planning for Digital Audio Broadcasting

2003

Matheuristics for the irregular bin packing problem with free rotations

2017

[EN] We present a number of variants of a constructive algorithm able to solve a wide variety of variants of the Two-Dimensional Irregular Bin Packing Problem (2DIBPP). The aim of the 2DIBPP is to pack a set of irregular pieces, which may have concavities, into stock sheets (bins) with fixed dimensions in such a way that the utilization is maximized. This problem is inspired by a real application from a ceramic company in Spain. In addition, this problem arises in other industries such as the garment industry or ship building. The constructive procedure presented in this paper allows both free orientation for the pieces, as in the case of the ceramic industry, or a finite set of orientation…

Reactive GRASP for the strip-packing problem

2008

This paper presents a greedy randomized adaptive search procedure (GRASP) for the strip packing problem, which is the problem of placing a set of rectangular pieces into a strip of a given width and infinite height so as to minimize the required height. We investigate several strategies for the constructive and improvement phases and several choices for critical search parameters. We perform extensive computational experiments with well-known instances which have been previously reported, first to select the best alternatives and then to compare the efficiency of our algorithm with other procedures. The results show that the GRASP algorithm outperforms recently reported metaheuristics.

A GRASP/Path Relinking algorithm for two- and three-dimensional multiple bin-size bin packing problems

2013

The three-dimensional multiple bin-size bin packing problem, MBSBPP, is the problem of packing a set of boxes into a set of bins when several types of bins of different sizes and costs are available and the objective is to minimize the total cost of bins used for packing the boxes. First we propose a GRASP algorithm, including a constructive procedure, a postprocessing phase and some improvement moves. The best solutions obtained are then combined into a Path Relinking procedure for which we have developed three versions: static, dynamic and evolutionary. An extensive computational study, using two- and three-dimensional instances, shows the relative efficiency of the alternatives considere…

Constructive procedures to solve 2-dimensional bin packing problems with irregular pieces and guillotine cuts

2015

Abstract This paper presents an approach for solving a new real problem in cutting and packing. At its core is an innovative mixed integer programme model that places irregular pieces and defines guillotine cuts. The two-dimensional irregular shape bin packing problem with guillotine constraints arises in the glass cutting industry, for example, the cutting of glass for conservatories. Almost all cutting and packing problems that include guillotine cuts deal with rectangles only, where all cuts are orthogonal to the edges of the stock sheet and a maximum of two angles of rotation are permitted. The literature tackling packing problems with irregular shapes largely focuses on strip packing i…

On Utilizing Stochastic Non-linear Fractional Bin Packing to Resolve Distributed Web Crawling

2014

This paper deals with the extremely pertinent problem of web crawling, which is far from trivial considering the magnitude and all-pervasive nature of the World-Wide Web. While numerous AI tools can be used to deal with this task, in this paper we map the problem onto the combinatorially-hard stochastic non-linear fractional knapsack problem, which, in turn, is then solved using Learning Automata (LA). Such LA-based solutions have been recently shown to outperform previous state-of-the-art approaches to resource allocation in Web monitoring. However, the ever growing deployment of distributed systems raises the need for solutions that cope with a distributed setting. In this paper, we prese…

Dual Inequalities for Stabilized Column Generation Revisited

2014

Column generation (CG) models have several advantages over compact formulations: they provide better linear program bounds, may eliminate symmetry, and can hide nonlinearities in their subproblems. However, users also encounter drawbacks in the form of slow convergence, also known as the tailing-off effect, and the oscillation of the dual variables. Among different alternatives for stabilizing the CG process, Ben Amor et al. [Ben Amor H, Desrosiers J, Valério de Carvalho JM (2006) Dual-optimal inequalities for stabilized column generation. Oper. Res. 54(3):454–463] suggest the use of dual-optimal inequalities (DOIs) in the context of cutting stock and bin packing problems. We generalize th…